home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2441 < prev    next >
Encoding:
Text File  |  1996-08-05  |  6.1 KB  |  168 lines
  1. Path: pm074-11.dialip.mich.net!user
  2. From: nkuitse@umich.edu (Paul M. Hoffman)
  3. Newsgroups: comp.lang.c,comp.sys.mac.programmer.tools
  4. Subject: Re: HELP ME PLEASE: Thesaurus function / Thesuarus lists needed
  5. Date: Sun, 21 Jan 1996 10:57:59 -0500
  6. Organization: University of Michigan
  7. Message-ID: <nkuitse-2101961057590001@pm074-11.dialip.mich.net>
  8. References: <4dj5ke$uo2@news.clandjop.com>
  9. NNTP-Posting-Host: pm074-11.dialip.mich.net
  10.  
  11. In article <4dj5ke$uo2@news.clandjop.com>, eday@clandjop.com wrote:
  12.  
  13. >I need to add a thesaurus function to a program. I need some
  14. >help/guidance in starting this project.
  15.  
  16. [snip]
  17.  
  18. >So, here I am, asking: Where can I go, who do I ask, what can I do to
  19. >get this project going?
  20.  
  21. I'm doing something similar, using data based on a Project Gutenberg
  22. edition of Roget's Thesaurus -- this is the last public-domain edition,
  23. from 1911, plus a few modern-day changes.  Here's a description from the
  24. file:
  25.  
  26. >*********************************************************************
  27. >**                       Thesaurus-1911                            **
  28. >**           Version 1.02  (supplemented: July 18, 1991)           **
  29. >*********************************************************************
  30. ><--  An electronic thesaurus derived from the version of Roget's
  31. >Thesaurus published in 1911.
  32. >     This thesaurus has been prepared by MICRA, Inc. (May 1991).
  33.  
  34. [snip]
  35.  
  36. >     Note that this version of Thesaurus-1911 has been supplemented
  37. >with over 1,000 words not present in the original 1911 edition, but
  38. >many modern words are still missing.  About 1500 verbs (out of 6500)
  39. >which can be found in an 80,000-word spell-checker are absent from
  40. >this work.
  41.  
  42. Here's one place to get it (URL from an Archie search in Anarchie):
  43.  
  44.   ftp://ftp.uu.net//doc/literary/gutenberg/etext91/roget14a.txt.Z
  45.  
  46. It's 600K or so, 1400K when uncompressed (use MacCompress).  It's split up
  47. by meaning into about 1000 entries, like its modern-day descendant,
  48. Roget's International Thesaurus.  Here's an example of (part of) an entry:
  49.  
  50. >     #45. [Connecting medium.] Connection. -- N. vinculum, link;
  51. >connective, connection; junction &c. 43; bond of union, copula, 
  52. >hyphen, intermedium[obs3]; bracket; bridge, stepping-stone, isthmus.
  53. >     bond, tendon, tendril; fiber; cord, cordage; riband, ribbon, 
  54. >rope, guy, cable, line, halser|, hawser, painter, moorings, wire,
  55. >chain; string &c. (filament) 205.
  56.  
  57. I have a cleaned-up version which I can make available if you're
  58. interested; it looks like this:
  59.  
  60. >#45. [Connecting medium] Connection
  61. ><N>
  62. >     @vinculum, link; connective, connection; junction <etc> 43;
  63. >bond of union, copula, hyphen, intermedium[<obs>]; bracket; bridge,
  64. >stepping-stone, isthmus.
  65. >     @bond, tendon, tendril; fiber; cord, cordage; riband, ribbon, 
  66. >rope, guy, cable, line, halser[<pipe>], hawser, painter, moorings, 
  67. >wire, chain; string <etc> (filament) 205.
  68.  
  69. Once you have the data, you need to do some serious Perl (or some such)
  70. coding.  One (relatively) quick and simple way to make it usable is as
  71. follows.
  72.  
  73. Generate an intermediate index by word, looking something like this:
  74.  
  75.   ...
  76.   bond          43 45 79 402 406 768
  77.   bondage       43 402 612
  78.   ...
  79.   Presbyterian  509 993
  80.   ...
  81.  
  82. (Use Perl associative arrays; it shouldn't be too hard, if perhaps a bit
  83. memory-intensive -- I give MacPerl 8M+ for scripts like this.  I can
  84. e-mail you sample Perl scripts if you like.)
  85.  
  86. Generate a hash table from this.  You might use a "dumb" hash table that
  87. doesn't resolve collisions: say that "bondage" and "Presbyterian" hash to
  88. the same slot, which points to a sequence of entry numbers that is the
  89. union of those for "bondage" and "Presbyterian":
  90.  
  91.   43 45 79 402 406 509 768 993
  92.  
  93. Read all those entries and discard the ones that don't contain the word
  94. "bondage".
  95.  
  96. You'll need an index that takes you from the entry number to its byte
  97. offset within the file.  Again, use Perl to create it:
  98.  
  99.   1 : 0
  100.   2 : 409
  101.   3 : 745
  102.   4 : 1074
  103.  
  104. Munge this into a Rez resource rescription (excuse my questionable syntax here):
  105.  
  106.   resource 'EDAT' 2000 {
  107.     0, 409, 745, 1074, ...
  108.   };
  109.  
  110. or to an array declaration in C, or whatever.
  111.  
  112. Lastly, put all of this stuff into "chunks" in the data fork of a file:
  113.  
  114.   1  <header, including offsets of chunks 2-5>
  115.   2  <hash table proper: each entry is an offset into chunk 3>
  116.   3  <entry number sequences referenced by the hash table>
  117.   4  <table mapping entry numbers to entry offsets within chunk 5>
  118.   5  <the thesaurus data itself>
  119.  
  120. Keep chunks 1, 2, 4 and (if you can) 3 in memory.  You might want a way to
  121. keep often-used parts of chunk 5 in memory, too, but that complicates
  122. things a little.  (Hint: use a simple cache, an array of pointers to, say,
  123. the 16 most recently used entries.  For people who like to "branch"
  124. through thesauri, this should make things much quicker.)
  125.  
  126. Et voila` (waving hands) you have a usable thesaurus!  Well, more or
  127. less.  The only really hard part should be the hash table: I've made
  128. collision resolution sound easy (by ignoring it), but you will run into
  129. problems if you're not careful.  Try using a variety of hash functions and
  130. pick the one that yields the best results.
  131.  
  132. Here's a pseudo-C skeleton of the look-up algorithm:
  133.  
  134.   Boolean LookUp (String word, StringArray results)
  135.   {
  136.     /* Return each entry that contains the specified word */
  137.     UnsignedInt h, entryNum;
  138.     Ptr p;
  139.     String entry;
  140.     Boolean success = false;
  141.  
  142.     h = HashWord (word) mod kHashTableSize;
  143.     for (each entryNum in slot h of the hash table) {
  144.       ReadEntryIntoString (entryNum, entry);
  145.       if (entry contains word) {
  146.         AddStringToArray (results, entry);
  147.         success = true;
  148.       }
  149.     }
  150.     return success;
  151.   }
  152.  
  153. This isn't the most elegant way to do it, but it's simple.  (Tempting
  154. alternative: use a separate resource for each entry.  Don't do it: it may
  155. sound good, but it looks like gross Resource Manager abuse to me.  A
  156. thousand resources is an awful lot.)
  157.  
  158. I love the smell of Perl-generated C code in the morning!
  159.  
  160. Good luck,
  161.  
  162. Paul.
  163.  
  164. -- 
  165. Paul Hoffman         | mailto:paul.hoffman@umich.edu
  166. Taubman Medical Lib. | http://www-personal.umich.edu/~nkuitse/
  167. Univ. of Michigan    | "Dragons do not enter into this message"
  168.